package com.leetcode.array;

import java.util.Scanner;
/**
 * Given an array of integers and an integer k,
 *  find out whether there are two distinct 
 *  indices i and j in the array such that 
 *  nums[i] = nums[j] and the difference between i 
 *  and j is at most k.
 * @author Adiy
 *
 */
public class ContainsDuplicateII {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
//		int k=in.nextInt();
//		int[] nums=new int[k];
//		for(int i=0;i<k;i++){
//			nums[i]=in.nextInt();
//		}
		int[] nums=new int[30000];
		for(int i=0;i<30000;i++){
			nums[i]=i;
		}
		int m=in.nextInt();
		boolean flag=containsDuplicate(nums,m);
		System.out.println(flag);

	}

	public static boolean containsDuplicate(int[] nums,int k){
		int i=0, j=nums.length-1;
		int len=j;
		int count=0;
		if(j<i) return false;
		while(i<=j){
			if(i<j){
				if(nums[i]==nums[j]&&j-i>k||nums[i]!=nums[j]) {
					  j--;continue;
					}
				if(nums[i]==nums[j]&&j-i<=k){
						count++;
						j=len;
						i++;
					}	
			}
			if(i==j){
				i++;j=len;
			}
			
		}
		if(count>0) {
			System.out.println(count);
			return true;
		}
		else return  false;
	}
}
